public class Sort {

    /**
     * 计数排序：
     * 时间复杂度：O(范围 + n )
     *       范围越大  越慢
     * 空间复杂度：O(范围)
     * 稳定性：
     * @param array
     */
    public static void countSort(int[] array) {

        // 1. 找到最大值和最小值，用来确定计数数组的大小
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }

        // 2. 创建计数数组

        int len = maxVal - minVal + 1;
        int[] count = new int[len];

        // 3. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数

        for (int i = 0; i < array.length; i++) {
            int index = array[i] - minVal;
            count[index]++;
        }
        // 4.依次 遍历计数数组  O(范围)
        int index = 0;
        for (int i = 0; i < len; i++) {
            while(count[i] != 0) {
                array[index++] = i + minVal;
                count[i]--;
            }
        }
    }
}
